//给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。 
//
// 示例 1 : 
//
// 
//输入: 2736
//输出: 7236
//解释: 交换数字2和数字7。
// 
//
// 示例 2 : 
//
// 
//输入: 9973
//输出: 9973
//解释: 不需要交换。
// 
//
// 注意: 
//
// 
// 给定数字的范围是 [0, 10⁸] 
// 
//
// Related Topics 贪心 数学 👍 445 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

//java:最大交换
public class Q0670MaximumSwap {
    public static void main(String[] args){
        Solution solution = new Q0670MaximumSwap().new Solution();
        solution.maximumSwap(1993);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maximumSwap(int num) {
        if (num < 0 || num > Math.pow(10, 8)) return -1;
        int[] digits = digitsOfNum(num);
        for (int i = 0; i < digits.length; i++) {
            int max = digits[i], maxIndex = i;
            for (int j = digits.length - 1; j > i; j--) {
                if (max < digits[j]) {
                    maxIndex = j;
                    max = digits[j];
                }
            }
            if (maxIndex != i) {
                swap(digits, i, maxIndex);
                return digitsToNum(digits);
            }
        }
        return num;
    }

    public int[] digitsOfNum(int num) {
        List<Integer> digitList = new ArrayList<>();
        if (num == 0) return new int[1];
        while (num > 0) {
            int digit = num % 10;
            digitList.add(digit);
            num = num / 10;
        }
        Collections.reverse(digitList);
        int[] digits = digitList.stream().mapToInt(x -> x).toArray();
        return digits;
    }

    public int digitsToNum(int[] digits) {
        if (digits == null || digits.length == 0) return 0;
        int res = 0;
        for (int i = digits.length - 1, mul = 1; i >= 0; i--, mul *= 10) {
            res = res + digits[i] * mul;
        }
        return res;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}